package com.ayuer.chapter08;

import java.util.Arrays;

public class ShellSortDemo {

    public static void main(String[] args) {
        //希尔排序
        int[] arr = {5, 4, 3, 2, 1, 0};
        shellSort(arr);

    }

    public static void shellSort(int[] arr) {

        for (int group = arr.length >>> 1; group > 0; group = group >>> 1) {
            //进行分组
            //插入排序
            //{5, 4, 3, 2, 1 ,0};
            for (int right = group; right < arr.length; right++) {
                //有序区域边界
                int seq = right - group;
                int curr = arr[right];
                while (seq >= 0 && arr[seq] > curr) {
                    arr[seq + group] = arr[seq];
                    seq -= group;
                }
                //插入
                arr[seq + group] = curr;
            }
        }

//        for (int right = 1; right < arr.length; right++) {
//            //有序区域边界
//            int seq = right - 1;
//            int curr = arr[right];
//            while (seq >= 0 && arr[seq] > curr) {
//                arr[seq + 1] = arr[seq];
//                seq--;
//            }
//            //插入
//            arr[seq + 1] = curr;
//
//        }
        System.out.println(Arrays.toString(arr));

    }
}
